package Work_oj;

import java.util.*;

public class test692 {
    public static class creatTree implements Comparator<Map.Entry<String,Integer>> {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            if(o1.getValue().compareTo(o2.getValue()) == 0) {
                return o2.getKey().compareTo(o1.getKey());
            }
            return o1.getValue().compareTo(o2.getValue());
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if(map.get(words[i]) == null) {
                map.put(words[i],1);
            } else {
                int size = map.get(words[i]) + 1;
                map.put(words[i],size);
            }
        }
        //要创建小根堆
        creatTree creat = new creatTree();
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(creat);
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                //当不足k个时 直接插入
                minHeap.offer(entry);
            } else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> ret = minHeap.poll();
            list.add(ret.getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
